public class MaxHeap <E extends Comparable<E>>{
    private Array<E> data;

    public MaxHeap() {
        data = new Array<>();
    }

    public MaxHeap(int capacity){
        data = new Array<>(capacity);
    }

    /**
     * 将一个数组初始化为最大堆
     * @param arr
     */
    public MaxHeap(E[] arr){
        data = new Array<>(arr);
        for (int i = parent(arr.length-1); i >= 0; i--) {
            siftDown(i);
        }
    }

    /**
     * 返回堆中的元素个数
     */
    public int size(){
        return data.getSize();
    }

    public boolean isEmpty(){
        return data.isEmpty();
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引
     * @param index
     * @return
     */
    private int parent(int index){
        if (index == 0){
            throw new IllegalArgumentException("index-0 doesn't have parent.");
        }
        return (index -1) / 2;
    }

    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引
     * @param index
     * @return
     */
    private int leftChild(int index){
        return index * 2 + 1;
    }
    /**
     * 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引
     * @param index
     * @return
     */
    private int rightChild(int index){
        return index * 2 + 2;
    }
    /**
     * 向堆中添加元素
     */
    public void add(E e){
        data.addLast(e);
        siftUp(data.getSize()-1);
    }

    /**
     * 向上调整堆以维护堆的性质。
     * 当插入一个新元素或删除一个元素后，这个方法用于重新调整堆，确保堆仍然满足最大堆或最小堆的性质。
     * @param k 新加入的元素的索引
     */
    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0){
            data.swap(k,parent(k));
            k = parent(k);
        }
    }

    /**
     * 查找并返回最大元素。
     * 该方法通过访问堆的根元素来找到最大值，因为最大堆的性质保证了根元素是堆中最大的。
     * 如果堆为空，则抛出IllegalArgumentException，表明无法在空堆中找到最大元素。
     *
     * @return 堆中的最大元素。
     * @throws IllegalArgumentException 如果堆为空，则抛出此异常。
     */
    public E findMax(){
        // 检查堆是否为空，如果为空则抛出异常
        if (data.getSize() == 0){
            throw new IllegalArgumentException("Can not findMax when heap is empty!");
        }
        // 返回堆中最大元素，即根元素
        return data.get(0);
    }

    /**
     * 从堆中提取最大元素。
     * <p>
     * 此方法首先找到堆中的最大元素，然后将其与堆底元素交换，接着移除堆底元素（即最大元素），
     * 最后通过向下调整堆顶元素来维护堆的性质。
     * <p>
     * 这一过程确保了堆的结构在移除最大元素后仍然满足最大堆的定义，即父节点的值不小于其子节点的值。
     *
     * @return 堆中的最大元素。
     */
    public E extractMax(){
        // 找到并保存堆中的最大元素
        E ret = findMax();

        // 将最大元素与堆底元素交换，准备移除最大元素
        data.swap(0, data.getSize()-1);
        // 移除堆底元素，即之前交换到堆底的最大元素
        data.removeLast();
        // 向下调整堆顶元素，以维护最大堆的性质
        siftDown(0);

        return ret;
    }

    /**
     * 向下调整堆以维护堆的性质。
     * 当插入一个新元素或删除一个元素后，这个方法用于重新调整堆，确保堆仍然满足最大堆或最小堆的性质。
     * 该方法通过比较父节点和其子节点的值，如果必要，将它们交换，直到恢复堆的性质。
     *
     * @param k 要调整的堆节点的索引，即父节点的索引。
     */
    private void siftDown(int k) {
        // 当左子节点存在时，持续调整堆
        while (leftChild(k) < data.getSize()) {
            // j为两个子树中元素较大的那个索引
            // 获取左子节点的索引
            int j = leftChild(k);
            // 如果右子节点存在且大于左子节点，选择右子节点
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChild(k);
            }
            // 如果父节点大于等于子节点，则堆的性质已满足，结束调整
            if (data.get(k).compareTo(data.get(j)) >= 0) {
                break;
            }
            // 否则，交换父节点和子节点，继续向下调整
            data.swap(k, j);
            k = j;
        }
    }
    /**
     * 取出堆中的最大元素，并且替换成元素e
     */
    public E replace(E e){
        E ret = findMax();
        data.set(0,e);
        siftDown(0);

        return ret;
    }

}
